#! /usr/bin/python

import math
import time
import random

tt = time.time()

UP = 4*10**7

def isPrime(n):
    if n ==2 or n==3 or n==5 or n==7: return True
    if n==1 or n%2 == 0 or n%3 == 0: return False
    for i in range(5, int(math.sqrt(n))+1, 6):
        if n%i == 0 or n%(i+2) == 0: return False
    return True

def gcd(a, b):
    if b == 0: return a
    return gcd(b, a%b)

def sieve(n):
    ll = range(n)
    for i in range(2, int(math.sqrt(n)) + 1):
	for j in range(i**2, n, i):
	    ll[j] = 0
    return [p for p in ll if p != 0]

primes = sieve(10**4)
table = [0 for i in range(UP)]
table[0:10] = [0, 1, 1, 2, 2, 4, 2, 6, 4, 6, 4]
primes.remove(1)
for p in primes:
    table[p] = p - 1

iterate(table)
print table.count(0)
iterate(table)
print table.count(0)

for i in range(12, 70000):
    if table[i] == 0: continue
    for p in primes:
	n = i*p
	if n > 4*10**7: break
	if table[n] != 0: continue	
	if i%p != 0:
	   table[n] = table[i]*(p-1)
	else: table[n] = table[i]*p

def chainLength(start, table):
    length = 2
    while start != 2:
	start = table[start]
	length += 1
    return length

maxi = 19999379

def iterate(table):
    for m in range(6, UP/2):
        if table[m] != 0:
	   if m%2 == 0 and table[2*m] == 0: table[2*m] = table[m]*2	
	   if m%2 != 0 and table[2*m] == 0: table[2*m] = table[m]
    for m in range(3, int(math.sqrt(UP))):
        n = m*(m+1)
	if table[n] == 0: table[n] = table[m]*table[m+1]
    for m in range(3, int(math.sqrt(UP)), 2):
        n = m*(m+2)
	if table[n] == 0: table[n] = table[m]*table[m+2]
    for m in range(4, int(math.sqrt(UP)), 2):
        n = m*(m+2)
	if table[n] == 0: table[n] = table[m]*table[m+2]*2

iterate(table)
print table.count(0)
iterate(table)
print table.count(0)
iterate(table)
print table.count(0)
iterate(table)
print table.count(0)

ss = 0
print table[0:100]

iterate(table)
print table.count(0)
iterate(table)
print table.count(0)

for i in range(len(table)):
    if table[i] == 0: 
	print i
	break


print time.time() - tt
